// 【题目】力扣1944. 队列中可以看到的人数
// 【难度】困难
// 【提交】https://leetcode.cn/problems/number-of-visible-people-in-a-queue/submissions/664836994/
// 【标签】栈；数组；单调栈

//
// Created by 1 on 2025/9/21.
//
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> res(n, 0);
        stack<int> st; // 单调递减栈，存储索引

        for (int i = 0; i < n; i++) {
            // 当前人的身高
            int h = heights[i];
            // 弹出所有比当前人矮的人，这些矮的人可以看到当前人
            while (!st.empty() && heights[st.top()] < h) {
                res[st.top()]++; // 栈顶的人能看到当前人
                st.pop();
            }
            // 如果栈非空，说明栈顶的人比当前人高（或相等）
            // 那么当前人也能被栈顶的人看到
            if (!st.empty()) {
                res[st.top()]++;
            }
            st.push(i);
        }
        return res;
    }
};